package com.lcm.algorithm.datatest.array.slidWindow;

/**
 * @description:
 * [209. 长度最小的子数组]
 *
 * 难度中等226收藏分享切换为英文关注反馈
 *
 * 给定一个含有 **n** 个正整数的数组和一个正整数 **s ，**找出该数组中满足其和 **≥ s** 的长度最小的连续子数组**。**如果不存在符合条件的连续子数组，返回 0。
 * 输入: s = 7, nums = [2,3,1,2,4,3]
 * 输出: 2
 * 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
 * @author: lcm
 * @create: 2020-04-05 09:55
 **/

public class MinSubArrayLen {

    public static void main(String[] args){
        int[] nums=new int[]{2,3,1,2,4,3};
        System.out.println(minSubArrayLen(7,nums));
    }

    /**
     * 1.暴力破解：遍历所有子数组，找到最短的，O(n^2)
     * 2.双指针法：想象成一个滑动窗口，left++是减少，right++是增大，编码需要注意边界值
     * @param s
     * @param nums
     * @return
     */
    public static int minSubArrayLen(int s, int[] nums) {
        int result=Integer.MAX_VALUE;
        int sum=0;
        for(int left=0,right=0;right<nums.length;right++){
            sum=sum+nums[right];
            while(sum>=s){
                result=Math.min(result,(right-left+1));
                sum=sum-nums[left];
                left++;
            }
        }
        return result==Integer.MAX_VALUE?0:result;
    }

}
